在資料結構中，通常 stack 都會和 queue 被放在一起討論。

既然有單調棧(monotonic stack)，那當然也有單調隊列(monotonic queue)。相對於單調棧，單調隊列的細節稍微多一點。單調隊列可以從兩端操作，因此像 python 會用 deque 的方式實現。

今天的範例題是 239. Sliding Window Maximum。這題也可以用滑動窗口（題目都告訴你了），不過我們姑且拿來練單調隊列。

首先當然是要維持一個隊列，這邊維持的是遞減的單調隊列。遇到比較小的數就 append 到最後，如果不是最小的，就一路 pop 直到符合性質為止。

假設目前的遞減隊列是 [a1, a2, a3, a4, a5]，如果新元素 a2 < b1 < a3，由於 a3, a4, a5 都是在 b1 前面進列，這三個數一定會在 b1 出去前被 pop 掉，所以無論如何不可能成為 b1 進列後的最大值，因此就可以直接被刪掉。假設 b2 是最大值，那所有數字都可以直接被清空。

最後，隊列可以存 index 方便確認範圍，以上就是關於這題解法的所有細節了。

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums:
            return []

        max_values = [0]*(len(nums)-(k-1)) 
        window = deque()

        for i in range(len(nums)):
            while window and window[0] < i - (k-1):
                window.popleft()

            while window and nums[i] >= nums[window[-1]]:
                window.pop()

            window.append(i)

            if i >= k - 1:
                max_values[i-(k-1)] = nums[window[0]]

        return max_values

• monotonic queue
  • 239. Sliding Window Maximum